<head>
    <meta charset="UTF-8">
<title>算法提高 进攻策略加强</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】<br />
<span style="font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px">　植物大战僵尸这款游戏中，还有一个特别的玩儿法：玩家操纵僵尸进攻植物。</span><br style="padding-bottom: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px; padding-top: 0px" />
<span style="font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px">　　首先，僵尸有m种（每种僵尸都是无限多的），玩家可以选择合适的僵尸来进攻。使用第i种僵尸需要花费Wi资源，可以得到Pi的攻击效果。在这里，我们认为多个僵尸总的攻击效果就是他们每个攻击效果的代数和。</span><br style="padding-bottom: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px; padding-top: 0px" />
<span style="font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px">　　地图共有n行，对于第i行，最左端有若干植物，这些植物需要至少Qi的攻击才能被全部消灭。若一行上的植物全部被消灭，我们称这一行被攻破。</span><br style="padding-bottom: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px; padding-top: 0px" />
<span style="font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px">　　由于资源紧张，你只有总量为K的资源，不一定能够攻破所有行。但统治者希望攻破相邻的T行，并希望T尽量的大。你能帮他算出T的值吗？</span><br />
【输入格式】<br />
<span style="font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px">第一行三个非负整数：m、n、K；</span><br style="padding-bottom: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px; padding-top: 0px" />
<span style="font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px">　　第二行m个正整数，第i个数表示Wi；</span><br style="padding-bottom: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px; padding-top: 0px" />
<span style="font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px">　　第三行m个正整数，第i个数表示Pi；</span><br style="padding-bottom: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px; padding-top: 0px" />
<span style="font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px">　　第四行n个非负整数，第i个数表示Qi。</span><br />
【输出格式】<br />
<span style="font-family: 'Courier New', FixedSys; color: rgb(32,0,0); font-size: 16px">3 11 39</span><br style="padding-bottom: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; font-family: 'Courier New', FixedSys; color: rgb(32,0,0); font-size: 16px; padding-top: 0px" />
<span style="font-family: 'Courier New', FixedSys; color: rgb(32,0,0); font-size: 16px">5 2 11</span><br style="padding-bottom: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; font-family: 'Courier New', FixedSys; color: rgb(32,0,0); font-size: 16px; padding-top: 0px" />
<span style="font-family: 'Courier New', FixedSys; color: rgb(32,0,0); font-size: 16px">3 1 7</span><br style="padding-bottom: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; font-family: 'Courier New', FixedSys; color: rgb(32,0,0); font-size: 16px; padding-top: 0px" />
<span style="font-family: 'Courier New', FixedSys; color: rgb(32,0,0); font-size: 16px">5 3 6 10 3 2 4 200 1 1 1</span><br />
【样例输入】<br />
一个满足题目要求的输入范例。<br />
例：<br />
2 2<br />
1 2<br />
3 4<br />
【样例输出】<br />
<span style="font-family: 'Courier New', FixedSys; color: rgb(32,0,0); font-size: 16px">4</span><br />
【数据规模和约定】</p>
<div style="padding-bottom: 0px; margin: 20px 0px 0px; padding-left: 0px; padding-right: 0px; font-family: 宋体, 'Times New Roman'; padding-top: 0px" id="pcont1">
<div style="padding-bottom: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; font-family: 'Times New Roman', 宋体; color: rgb(32,0,0); font-size: 14px; padding-top: 0px" class="pdcont">　对于70%的数据：n&lt;=1000<br style="padding-bottom: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px" />
<br style="padding-bottom: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px" />
对于100%的数据：n&lt;=200000，m&lt;=100，K&lt;=1000000，所有Pi、Qi&lt;=100000000</div>
<div>&nbsp;</div>
</div>